package org.everyday;

import cn.hutool.core.lang.Assert;
import com.common.TreeNode;

/**
 * @Author: Tang World
 * @Date: 2/9/2022 上午9:38
 */
public class L687 {
    int ans = 1;

    public int longestUnivaluePath(TreeNode root) {
        // 从该root开始计算，然后递归
        if (root == null) return 0;
        dfs(root);
        return ans;
    }

    int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int rootLeft = dfs(root.left);// 以root.left为根的结果。
        int rootRight = dfs(root.right);
        int left = 0, right = 0; // 以root为根的结果
        if (root.left != null && root.left.val == root.val) {
            left = rootLeft + 1;
        }
        if (root.right != null && root.right.val == root.val) {
            right = rootRight + 1;
        }
        ans = Math.max(ans,left+right);
        return Math.max(left,right);
    }

    public static void main(String[] args) {
        L687 l687 = new L687();
        TreeNode root = TreeNode.buildTree(new Integer[]{2, 1, 3, null, 4, null, null, null, null, 4, 4});
        int i = l687.longestUnivaluePath(root);
        Assert.isTrue(i == 2);
    }
}
